package com.leetcode.binary_search;

/**
 * @author Dennis Li
 * @date 2020/7/23 22:59
 */
public class MySqrt_69 {

    public int mySqrt(int x) {
        if (x <= 1) return x;
        int i = 0, j = x;
        while (i < j - 1) {
            int mid = i + (j - i) / 2;
            // 要用除法而不是乘法
            if (x / mid > mid)
                i = mid;
            else if (x / mid == mid)
                return mid;
            else
                j = mid;
        }
        return i;
    }

}
